This application relates to analysis of integrated circuits.
Circuits may be viewed as networks of nodes and circuit elements connected between nodes. As such, circuits may be analyzed based on a nodal analysis where a nodal equation may be written for each node based on the conservation of charge at the node, i.e., the total current entering the node is equal to the total current leaving the node (the Kirchoff's second rule). For a circuit with N nodes, N equations for the N nodes can be expressed in terms of the properties of circuit elements such as resistance, capacitance, and inductance, and in terms of the node voltages and currents. These N equations can be written into a matrix equation and are solved using various matrix approaches such as LU decompositions.
Integrated circuits with transistors can be simulated using direct methods such as LU decompositions. One example, the Berkeley SPICE2 simulator and its variations use LU decompositions to solve for circuit equations for circuits with transistors. See, Nagal, “Spice2: A computer program to simulate semiconductor circuits,” Tech. Rep. ERL M520, Electronics Research Laboratory Report, UC Berkeley (1975). The direct simulation methods may become less effective and can reach their computational limits when the number of transistors and other elements in circuits approaches the capacity limit, e.g., around 50,000 transistors for some direct simulation methods. This is in part because the super linear complexity O(n1.5) increases with the number of circuit nodes, n, and the amount of the extracted interconnect data for a large n can exceed the capacity of the software based on a direct simulation method.